package sort_1106;

import java.util.Arrays;
import java.util.Random;

public class Sort {
    /**
     * 插入排序
     *
     * 时间复杂度：
     * 最好情况：O(n) 当 数组已经有序
     * 最坏情况：O(n^2) 当 数据是逆序
     * 平均情况：O(n^2)
     * 对于插入排序，数组越趋于有序，耗时越少
     *
     * 空间复杂度：
     * 最好/平均/最坏：O(1)
     *
     * 稳定性：稳定
     * @param array
     */
    public static void insert2(long[] array) {
        for (int i = 1; i < array.length; i++) {    // 循环 n - 1 次
            // 有序区间: [0, i)
            // 无序区间: [i, array.length)

            long x = array[i];
            int j;
            for (j = i - 1; j >= 0 && array[j] > x; j--) {
                array[j + 1] = array[j];
            }

            array[j + 1] = x;
        }
    }

    public static void insertSort(long[] array) {
        // 要对 array.length 个元素做排序，需要多少次 查找+插入 的过程？
        // array.length - 1

        // 外层的循环：需要进行很多次的 查找+插入
        for (int i = 0; i < array.length - 1; i++) {
            // 有序区间
            // 第一次（i == 0）： [0, 0] / [0, 1)
            // 第二次（i == 1）： [0, 1] / [0, 2)
            // ...
            // 第 i - 1 次（i）： [0, i] / [0, i + 1)

            // 有序区间：[0, i]
            // 无序区间：[i + 1, array.length)
            // 要插入的元素的下标是无序区间的第一个元素（紧挨着有序区间的下一个元素）
            long x = array[i + 1];

            // 查找并插入，遍历整个有序区间: [0, i]
            int j;
            for (j = i; j >= 0 && array[j] > x; j--) {
                array[j + 1] = array[j];
            }
            array[j + 1] = x;
        }
    }

    public static void 查找并插入整理版本(long[] array, int index) {
        // 有序区间: [0, index)
        long x = array[index];

        int i;
        for (i = index - 1; i >= 0 && array[i] > x; i--) {
            array[i + 1] = array[i];
        }
        array[i + 1] = x;
    }

    public static void 查找并插入(long[] array, int index) {
        // [0, index) 有序的
        // [index] 这个下标的元素就是要被插入的元素

        long x = array[index];
        // 从后往前进行 有序区间 的遍历
        int i;
        for (i = index - 1; i >= 0; i--) {
            long e = array[i];

            if (e > x) {
                // 说明 x 应该插入到 e 的前面去（并不一定挨着）
                // 把 e 往后搬，给 x 腾地方
                array[i + 1] = array[i];
            } else {
                // x 已经成功找到合适的位置并且插入了，不需要继续遍历有序区间了
                break;
            }
        }

        // 如果整个区间都遍历完之后，x 还是没有找到合适的位置，说明 x 比第一个元素还小
        // 把 x 放在最开始
        // 当上述循环因为这个条件（i >= 0）不满足结束的循环，则 i 一定是 -1
        // 否则，一定是由于 break 退出的循环，则 i >= 0
        if (i == -1) {
            array[0] = x;
        } else {
            // 说明 x 应该插入到 e 的后边（紧挨着）
            // e 的下标是 i，紧挨着的下标是 i + 1
            array[i + 1] = x;
        }
    }

    public static void swap(long[] array, int i, int j) {
        long t = array[i];
        array[i] = array[j];
        array[j] = t;
    }

    /**
     * 冒泡排序：
     *
     * 时间复杂度：
     * 最好情况：O(n) 当 数组已经有序
     * 平均情况：O(n^2)
     * 最坏情况：O(n^2)  当 数组是逆序的
     *
     * 空间复杂度：
     * 最好/平均/最坏：O(1)
     *
     * 稳定性：具备稳定性
     * @param array
     */
    public static void bubbleSort(long[] array) {
        for (int i = 0; i < array.length - 1; i++) {    // 需要 n - 1 次冒泡过程
            // 无序区间 [0, array.length - i)
            // 遍历整个无序区间，但是确保相邻的元素两两比较，所以
            // 要遍历的下标范围 [0, array.length - i - 1)

            // 每次冒泡过程时，假设无序区间是有序的
            boolean sorted = true;

            for (int j = 0; j < array.length - i - 1; j++) {
                if (array[j] > array[j + 1]) {
                    // 这里不加等号，加等号就失去稳定性
                    swap(array, j, j + 1);

                    sorted = false;     // 存在 前面的元素 > 后边的元素，说明假设无序区间有序的假设不成立

                    // 冒泡的过程中，一旦发生了交换，说明
                    // 存在：相邻的两个元素之间，前面的元素 > 后边的元素
                    // 反过来说：单次冒泡给过程，如果一次交换都没有发生过
                    // 说明不存在：相邻的两个元素之间，前面的元素 > 后边的元素
                    // 任意相邻的两个元素之间，前面的元素 <= 后边的元素
                    // 冒泡过程只在无序区间进行
                    // 无序区间的任意相邻的两个元素满足：前面的元素 <= 后边的元素
                    // 我们认为的无序区间是有序的
                    // 所以，整个数组已经全部是有序的了
                }
            }

            // 冒泡过程完成之后，如果 sorted == true，说明一次交换没发生过
            if (sorted) {
                return;
            }
        }
    }

    public static void selectSort(long[] array) {
        for (int i = 0; i < array.length - 1; i++) {    // 一共进行 n - 1 次选择过程
            // [无序区间] [有序区间]
            // 无序区间: [0, array.length - i)
            // 有序区间: [array.length - i, array.length)

            // 1. 遍历整个无序区间，找到最大的元素所在的下标（不需要知道最大的元素是多少，而是它在哪）
            int maxIdx = 0;
            // 在剩余位置，继续找比 array[maxIdx] 元素还大的元素
            for (int j = 1; j < array.length - i; j++) {
                // 期间，如果出现更的元素，则更新最大元素所在下标
                if (array[j] > array[maxIdx]) {
                    maxIdx = j;
                }
            }

            // 最大的元素在 [maxIdx]，即 array[maxIdx] 是无序区间的最大元素
            // 把最大的元素放到无序区间的最后一个位置
            // [0, array.length - i)
            // 无序区间的最后一个位置下标是 [array.length - i - 1]
            swap(array, maxIdx, array.length - i - 1);
        }
    }

    /**
     * 选择排序：
     *
     * 时间复杂度：
     * 最好/平均/最坏：O(n^2)
     *
     * 空间复杂度：
     * 最好/平均/最坏：O(1)
     *
     * 稳定性：保证不了稳定性
     * @param array
     */
    public static void selectSort2(long[] array) {
        for (int i = 0; i < array.length - 1; i++) {
            // 有序区间: [0, i)
            // 无序区间: [i, array.length)

            int minIdx = i;
            for (int j = i + 1; j < array.length; j++) {
                if (array[j] < array[minIdx]) {
                    minIdx = j;
                }
            }

            // 交换 [minIdx] 和 [i] 位置的元素
            swap(array, minIdx, i);
        }
    }

    public static void main2(String[] args) {
        long[] array = { 6, 1, 3, 5, 2, 8, 9, 4, 0, 7 };

        selectSort2(array);

        System.out.println(Arrays.toString(array));
    }

    // [from, to)
    public static void bubbleSort递归版本(long[] array, int from, int to) {
        int size = to - from;
        if (size <= 1) {
            return;
        }

        for (int i = from; i < to - 1; i++) {
            if (array[i] > array[i + 1]) {
                swap(array, i, i + 1);
            }
        }

        // [from, to)
        // [from, to - 1) 无序
        // [to - 1, to)   有序
        // 再用相同的方式处理剩余的问题
        bubbleSort递归版本(array, from, to - 1);
    }

    // 有序区间: [from, to)
    public static void insertSort递归版本(long[] array, int from, int to) {
        int size = to - from;   // 有序区间的长度
        // 无序区间的长度 array.length - size
        if (array.length - size <= 1) {
            return;
        }

        // [from, to)
        // 要插入的元素一定在 [to]
        long x = array[to];
        int i;
        for (i = to - 1; i >= 0 && array[i] > x; i--) {
            array[i + 1] = array[i];
        }

        array[i + 1] = x;

        // [from, to + 1) 有序了
        insertSort递归版本(array, from, to + 1);
    }

    // 无序区间: [from, to)
    public static void selectSort递归版本(long[] array, int from, int to) {
        // [无序][有序]
        int size = to - from;
        if (size <= 1) {
            return;
        }

        int maxIdx = from;
        for (int i = from + 1; i < to; i++) {
            if (array[i] > array[maxIdx]) {
                maxIdx = i;
            }
        }

        swap(array, maxIdx, to - 1);

        // 无序区间: [from, to - 1)
        selectSort递归版本(array, from, to - 1);
    }

    public static void 带有间隔的区间插排() {
        long[] array = { 1, 5, 3, 9, 2, 8, 4, 7, 6, 3, 2, 0, 3 };
        int gap = 3;

        for (int j = 0; j < 4; j++) {
            long x = array[gap * j + gap];
            int i;
            for (i = gap * j; i >= 0 && array[i] > x; i -= gap) {
                array[i + gap] = array[i];
            }

            array[i + gap] = x;
        }
    }

    public static void main3(String[] args) {
        Random random = new Random();
        for (int i = 0; i < 20; i++) {
            System.out.printf("%d, ", random.nextInt(50));
        }

        System.out.println();
    }

    /**
     * 希尔排序
     *
     * 时间复杂度: O(n ^ 1.25)
     *
     * 空间复杂度: O(1)
     *
     * 稳定性: 不稳定
     * @param array
     */
    public static void shellSort(long[] array) {
        if (array.length == 0) {
            return;
        }
        int gap = array.length / 2;
        while (true) {
            // 带有间隔的分组插排
            for (int i = gap; i < array.length; i++) {
                long x = array[i];
                int j;
                for (j = i - gap; j >= 0 && array[j] > x; j = j - gap) {
                    array[j + gap] = array[j];
                }

                array[j + gap] = x;
            }

            if (gap == 1) {
                // 说明上一次的分组插排其实最终的插排
                break;
            }

            gap = gap / 2;
        }
    }

    public static void adjustDown大堆(long[] array, int size, int index) {
        while (2 * index + 1 < size) {
            int maxIdx = 2 * index + 1;
            if (maxIdx + 1 < size && array[maxIdx + 1] > array[maxIdx]) {
                maxIdx++;
            }

            if (array[index] >= array[maxIdx]) {
                return;
            }

            swap(array, index, maxIdx);

            index = maxIdx;
        }
    }

    public static void createHeap大堆(long[] array, int size) {
        for (int i = (size - 2) / 2; i >= 0; i--) {
            adjustDown大堆(array, size, i);
        }
    }

    public static void heapSort(long[] array) {
        // 将整个数组（整个数组都是无序区间）创建成大堆
        createHeap大堆(array, array.length);

        // 循环选择的过程，一共需要 n - 1 次
        for (int i = 0; i < array.length - 1; i++) {
            // 无序区间: [0, array.length - i)
            // 交换最大的元素（下标是 [0]）和无序区间的最后一个元素（下标是 array.length - i - 1）
            swap(array, 0, array.length - i - 1);
            // 由于最大的元素已经放到最后了，所以，无序区间：[0, array.length - i - 1)
            // 无序区间的元素个数: array.length - i - 1 - 0 = array.length - i - 1
            // 为了维护无序区间的大堆性质，对无序区间剩余的元素，在 [0] 做向下调整
            adjustDown大堆(array, array.length - i - 1, 0);
        }
    }

    public static void main(String[] args) {
        long[] array = {3, 9, 1, 4, 5, 8, 2, 6, 0, 7};
        heapSort(array);

        System.out.println(Arrays.toString(array));
    }
}
